Trellis-enhanced precoding for trellis-coded transmission over channels with intersymbol interference allows coding and shaping gains to be achieved with minimal transmit power penalty for arbitrary signal constellations, provided the intersymbol interference channels are linearly invertible. This technique was proposed during the development of the V.34 Recommendation by the International Telecommunications Union-Telecommunications Standardization Sector (ITU-T) for voiceband modems for data transmission over the general switched telephone network (ITU-T Recommendation V.34, "Data communication over the telephone network. A modem operating at data signalling rates of up to 28800 bit/s for use on the general switched telephone network and on leased point-to-point 2-wire telephone-type circuits", September 1994).
Trellis-enhanced precoding can be employed for trellis-coded transmission over a variety of communication channels. However, if the channel response exhibits spectral nulls, trellis-enhanced precoding cannot be applied because the corresponding inverse precoding operation at the receiver requires inverse channel filtering. For channels with a spectral null, this inverse operation can result in unlimited error propagation. One important application where spectral nulls in the transmission channel are encountered is data transmission at rates of several Mbit/s over metallic cables, e.g., over shielded or unshielded twisted-pair cables in office environments. In this case, the line-coupling transformers at both cable ends introduce a spectral null at dc. In addition, spectral nulls or near nulls may be encountered as a result of severe signal attenuation by the cable. Alternatively, spectral nulls may be introduced intentionally by signal shaping filters designed to achieve desired channel response characteristics and/or to comply with regulations for electromagnetic compatibility.
PCM "56 kbit/s" voiceband modems represent another example for equipment in which spectral nulls in the transmission channel prevent the use of state-of-the-art trellis-enhanced preceding. This latest generation of voiceband modems exploits the fact that today's general switched telephone network constitutes an essentially digital network, transporting PCM-encoded voiceband signals, or data, at a rate of 64 kbit/s. If "server" modems are connected digitally to the network, there is only one analog local loop between the "client" modem and the rest of the network. The resulting overall channel is a baseband channel with almost 4 kHz bandwidth, a spectral null at dc, and possibly strong attenuation at 4 kHz. Although precoding in the downstream direction does not appear to be possible because modulation amplitudes must be equal to A/.mu. law PCM code levels, a preceding technique that allows transmission over channels with spectral nulls at dc and 4 kHz can be useful for upstream transmission.
Let the response of a discrete-time intersymbol-interference channel with additive noise be h(D)=1+h.sub.1 D+h.sub.2 D.sup.2 . . . and assume that h(D) is known at the transmitter. Assume further that for any two modulation symbols a.sup.i .epsilon., a.sup.k .epsilon.: a.sup.i .ident.a.sup.k mod .LAMBDA..sub.0 holds, where .OR right..LAMBDA..sub.0 +.lambda. is a finite set of modulation symbols into which information is encoded, .LAMBDA..sub.0 denotes the lattice underlying , and .lambda. is a given, possibly non-zero, offset value. The aim of all precoding techniques, without and with coding, is to determine a pre-equalized sequence of transmit signals x(D)=u(D)/h(D) such that, in the absence of noise at the channel output, an apparently intersymbol-interference free sequence of modulation symbols in a subset with elements in '.OR right..LAMBDA..sub.0 +.lambda. is received. To achieve this with channel inputs constrained to a given finite signal region, the set ' must be larger than the set . This output redundancy can then be employed to satisfy the constraint on the channel inputs. It is important that at the receiver an inverse precoding operation can be performed to retrieve from u(D) uniquely the encoded information. In the case of systems employing trellis coded modulation (TCM; cf. G. Ungerboeck, "Channel coding with multilevel/phase signals," IEEE Trans. Inform. Theory, vol. IT-28, pp. 55-67, January 1982), the sequence u(D) has to be a valid trellis-code sequence. In a system with preceding, the elements of the transmit signal sequence x(D) do not have to be discrete-valued modulation symbols.
Precoding for intersymbol-interference channels, without and with trellis-coded modulation, was proposed in the following publications:
(a) M. Tomlinson, "New automatic equalizer employing modulo arithmetic," Electron. Lett., vol. 7, pp. 138-139, March 1971 PA0 (b) H. Harashima and H. Miyakawa, "Matched transmission technique for channels with intersymbol interference," IEEE Trans. Commun., vol. 30, pp. 774-780, August 1972 PA0 (c) M. V. Eyuboglu and G. D. Forney, Jr., "Trellis preceding: Combined coding, preceding and shaping for intersymbol interference channels," IEEE Trans. Inform. Theory, vol. 38, pp. 301-314, March 1992. PA0 (d) R. Laroia, S. A. Tretter, and N. Farvardin, "A simple and effective precoding scheme for noise whitening on intersymbol interference channels," IEEE Trans. Commun., vol. 41, pp. 460-463, October 1993. PA0 (e) R. Laroia, "Coding for intersymbol interference channels--Combined coding and preceding," IEEE Trans. Inform. Theory, vol. 42, pp. 1053-1061, July 1996.
The first precoding technique, proposed in the first two of the above-mentioned publications, is called Tomlinson-Harashima (TH) precoding and was defined for uncoded systems. TH precoding employs memoryless modulation operations in the transmitter and the receiver to reduce transmit signals and decoded received signals to a finite signal region containing . In principle, TH preceding can work for arbitrary sets of modulation symbols. However, unless it is possible to define a power-efficient modulo extension of the original signal region containing , the advantages of TH preceding will be offset by losses of signal power efficiency. A power-efficient extension exists only if the entire signal space can be "tessellated" with translated and/or rotated versions of the original finite signal region without leaving empty spaces.
A first straightforward application of TH precoding to a system with trellis coding was proposed by Eyuboglu and Forney in the third of the above-mentioned publications. For this scheme it is necessary that a power-efficient modulo extension exists not only for the symbol set , but also for each of the subsets of that are obtained by set partitioning of and are needed to define trellis-code sequences. This limitation on the permissible shapes of signal sets was overcome by "flexible preceding", proposed by R. Laroia, S. A. Tretter, and N. Farvardin. In flexible preceding, a precoder adds to a sequence a(D) of transmit symbols in the smallest "dither" signals for which at the channel output a uniquely decodable symbol sequence u(D), with elements u.sub.n .epsilon., is obtained. For inverse precoding at the receiver the channel must be linearly invertible, otherwise unlimited error propagation can occur.
When flexible preceding is combined with trellis coding, a transmit power penalty of .apprxeq..DELTA..sub.m+1.sup.2 /12 results, where .DELTA..sub.m+1 represents the minimum intra-subset distance (MSSD) at the final partitioning level m+1. For small signal sets or deeper levels of subset partitioning, this penalty can significantly lower the effective coding gain. During the development of the V.34 Recommendation in 1993, the transmit power penalty was reduced to .DELTA..sub.0.sup.2 /12 by "trellis-enhanced preceding". For briefly describing this technique, let the first-level subsets of be .sub.0 and .sub.1, with MSSD .DELTA..sub.1. At time n, let y.sub.n.sup.0 .epsilon.{0,1} denote a trellis-code state bit that determines membership of the next valid code symbol either in .sub.0 or .sub.1. With trellis-enhanced preceding, which represents a combination of "flexible preceding" with feedback TCM encoding, trellis encoding is performed in two steps. In the first step, information is encoded into a transmit signal composed of a modulation symbol a.sub.n .epsilon..sub.0 or a.sub.n .epsilon..sub.1 and a smallest dither signal such that at the channel output a signal u.sub.n .epsilon..sub.y.sbsb.u.spsb.0 is obtained. The signal u.sub.n represents a valid continuation of the sequence u(D) from the given TCM state at time n. In the second "feedback" step, the encoder determines from u.sub.n the next TCM state at time n+1. This technique is described in the fifth of the above-mentioned publications.
A method to combat error propagation in the receiver of a transmission system using trellis-enhanced precoding for a channel with spectral nulls was proposed by G. Cherubini, S. Ol.cedilla.er, and G. Ungerboeck in "Increasing margins for 100BASE-T2: Introducing Trellis Coding," Contribution to IEEE 802.3 100BASE-T2 Task Force, Maui, Hi., Jul. 9-12, 1995. The method is based on the knowledge that, at time n, the element X.sub.n of the sequence x(D) of transmit signals is confined to a well-defined signal region X.sub.y.sbsb.n.spsb.0. This notation indicates that the signal regions depend on whether the symbol a.sub.n .epsilon..sub.y.sbsb.n.spsb.0 is taken from subset .sub.0 or .sub.1. When during inverse precoding the obtained estimated transmit signal x.sub.n exceeds the region X.sub.y.sbsb.n.spsb.0, clearly error propagation occurs. In this case, x.sub.n is limited to the region to which the actually transmitted signal is confined, i.e., x.sub.n is replaced by a new signal value that represents the orthogonal projection of x.sub.n onto the contour of the region X.sub.y.sbsb.n.spsb.0.
A similar, but not identical method was described in the publications by R. Fischer and J. Huber, "Comparison of precoding schemes for digital subscriber lines," IEEE Trans. Commun., vol. 45, pp. 334-343, March 1997 and by R. Fischer, "Using flexible precoding for channels with spectral nulls," IEE Electronics Letters, vol. 31, pp. 356-358, 2nd March 1995,